package com.hao.sort;

import java.util.Random;

/**
 * TODO
 *
 * @author 97472
 * @version 1.0
 * @date 2021/5/17 14:51
 */
public class QuickSort {
    public static void main(String[] args) {
        Random random = new Random();
        Integer[] arr = new Integer[10000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10000000);
        }
        long start1 = System.currentTimeMillis();
        pitQuickSort(arr);
        long end1 = System.currentTimeMillis();
        System.out.println("花费时间："+(end1-start1));
    }
    // 交换数组元素
    public static void swap(Integer[] arr,Integer index1,Integer index2){
        Integer temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    public static void swapQuickSort(Integer[] arr){
        swapQuickSort(arr,0, arr.length-1);
    }
    /**
     * 两端扫描交换快速排序
     * @param arr
     * @param left
     * @param right
     */
    private static void swapQuickSort(Integer[] arr,Integer left,Integer right){
        // 递归的边界条件
        if (left < right){
            // 中轴元素
            Integer pivot = arr[left];
            // [left,i] 为小于中轴元素的元素
            Integer i = left + 1;
            // [j，right] 为大于于中轴元素的元素
            Integer j = right;
            // i == j 是交换后同时指向同一个元素，但是还没有与中轴元素比较
            // 循环跳出来后一定，arr[i]第一个大于中轴元素，arr[j]最后一个小于中轴元素
            while (i <= j){
                while (i <= j && arr[i] <= pivot){
                    i++;
                }
                while (i <= j && arr[j] > pivot){
                    j--;
                }
                if (i <= j){
                    swap(arr,i,j);
                    i++;
                    j--;
                }
            }
            // 将pivot与arr[j]交换
            swap(arr,left,j);
            // 最后将两边的分组数组再进行快速排序.直到只剩一个元素
            swapQuickSort(arr,left,j-1);
            swapQuickSort(arr,j+1,right);
        }
    }
    public static void pitQuickSort(Integer[] arr){
        pitQuickSort(arr,0, arr.length-1);
    }
    /**
     * 两端扫描交换快速排序
     * @param arr
     * @param left
     * @param right
     */
    private static void pitQuickSort(Integer[] arr,Integer left,Integer right){
        // 递归的边界条件
        if (left < right){
            // 中轴元素
            Integer pivot = arr[left];
            // [left,i] 为小于中轴元素的元素
            Integer i = left;
            // [j，right] 为大于于中轴元素的元素
            Integer j = right;
            // 当i == j时循环结束
            while (i < j){
                while (i < j && arr[j] > pivot){
                    j--;
                }
                arr[i] = arr[j];
                while (i < j && arr[i] <= pivot){
                    i++;
                }
                arr[j] = arr[i];
            }
            // 结束循环后i == j 都指向这个坑，将中轴元素放入
            arr[i] = pivot;
            // 最后将两边的分组数组再进行快速排序.直到只剩一个元素
            pitQuickSort(arr,left,i-1);
            pitQuickSort(arr,i+1,right);
        }
    }
    public static void printlnArr(Integer[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" " + arr[i]);
        }
        System.out.println();
    }
}
